package com.fml.leecode.eaysy;



/**
 * 将两个 升序 链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 两个链表的节点数目范围是 [0, 50]
 * -100 <= Node.val <= 100
 * l1 和 l2 均按 非递减顺序 排列
 */
public class Demo21 {

    // 递归
    public  ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if (null == list1) {
            return list2;
        }
        if (null == list2) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list2.next, list1);
            return list2;
        }


    }


    public  ListNode mergeTwoLists1(ListNode list1, ListNode list2) {

        if (null == list1 || null == list2) {
            return null != list1 ? list1 : list2;
        }

        //存储所有数据,创建一个表头
        ListNode list = new ListNode();
        //临时变量，存储当前的数据
        ListNode temp = list;
        //退出循环条件
        while (null != list1 && null != list2) {
            //假设 list1不为空
            //获取首位较小的，假设list1较小
            if (list1.val < list2.val) {
                //存储数据，第一次赋值时，list 与 temp 指向的地址相同，值相同
                //第二次开始，数据覆盖在当前数据的地址上，链表结构。即等同于list后续指向temp数据
                // 数据结构又忘了，该复习了
                temp.next = list1;
                list1 = list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            //获取当前链表的 下一个数据，下次循环使用
            temp = temp.next;
        }
        //有一个为空，剩下一个收尾
        temp.next = list1 != null ? list1 : list2;

        return list.next;
    }


    // Definition for singly-linked list.
    class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

}


